home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / tsql / doc / tsql.mail / 000104_kline _Mon May 3 00:35:43 1993.msg < prev    next >
Internet Message Format  |  1996-01-31  |  10KB
  1. Received: from cheltenham.CS.Arizona.EDU by optima.CS.Arizona.EDU (5.65c/15) via SMTP
  2.     id AA24317; Mon, 3 May 1993 00:35:45 MST
  3. Date: Mon, 3 May 1993 00:35:43 MST
  4. From: "Nick Kline" <kline>
  5. Message-Id: <199305030735.AA16352@cheltenham.cs.arizona.edu>
  6. Received: by cheltenham.cs.arizona.edu; Mon, 3 May 1993 00:35:43 MST
  7. To: tsql
  8. Subject: updated valid-time aggregate defs
  9.  
  10. I've updated the definitions concerning valid-time partitioning in response
  11. to several comments.
  12.  
  13. I eliminated the definitions for partitioning attribute and value partioning
  14. since these are not temporal database aspects.  They were include for
  15. completeness before.
  16.  
  17. I have tried to more clearly explain the motivations behind having an
  18. *associated interval* with each valid-time temporal element (TE).
  19. I actually partition the time-line into TE's and associate with each TE an
  20. interval.  The reason for this association is two-fold: 
  21.     1) it's useful for the subdivision of the valid time-line to be
  22.         a partitioning (in the mathematical sense)
  23.     2) it's very useful to allow overlapping intervals and this is excluded
  24.         by pt. 1 above
  25.  
  26. Defining the terms this way is very general, yet it allows succinct
  27. definitions (excluding the long discussions!).
  28.  
  29. The revised definitions follow.
  30.  
  31. Please contact me with any correspondence.
  32.  
  33. Thanks,
  34.  
  35. Nick Kline
  36. kline@cs.arizona.edu
  37.  
  38. % Document Type: LaTeX
  39. \documentstyle[11pt]{article}
  40. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  41. % VARIOUS MACROS
  42. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  43.  
  44. \long\def\comment#1{}
  45. \newcommand{\entry}[1]{\subsubsection*{#1}}
  46.  
  47. \addtolength{\textwidth}{1.485in}%{1.2in}
  48. \setlength{\oddsidemargin}{.1in}%{.3in}
  49. \setlength{\evensidemargin}{.1in}%{.3in}
  50. \addtolength{\topmargin}{-.85in} %{-1.35in}
  51. \addtolength{\textheight}{1.8in} %{2.8in}
  52.  
  53. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  54. % PAPER START
  55. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  56.  
  57. \begin{document}
  58.  
  59. \subsection{Valid-time Partitioning}
  60.  
  61. {\em Valid-time partitioning} is the partitioning (in the mathematical
  62. sense) of the valid time-line into {\em valid-time elements}.  For
  63. each valid-time element, we associate an interval of the valid
  64. time-line on which a cumulative aggregate may then be applied.  
  65.  
  66. \entry{Alternative Names}
  67.  
  68. Valid-time grouping.
  69.  
  70. \entry{Discussion}
  71.  
  72. To compute the aggregate, first partition the time-line into
  73. valid-time elements, then associate an interval with each valid-time
  74. element, assemble the tuples valid over each interval, and finally
  75. compute the aggregate over each of these sets.  The value at any event
  76. is the value computed over the partitioning element that contains that
  77. event.
  78.  
  79. The reason for the {\em associated} interval with each temporal
  80. element is that we wish to perform a {\em partition} of the valid
  81. time-line, and not exclude certain queries.  If we exclude computing
  82. the aggregate on overlapping intervals, we exclude queries such as
  83. ``Find the average salary paid for one year before each hire.''  Such
  84. queries would be excluded because the one-year intervals before each hire
  85. might overlap.
  86.  
  87.  
  88. Partitioning the time-line is a useful capability for aggregates in
  89. temporal databases (+R1,+R3).
  90.  
  91. Grouping is inappropriate because the valid-time elements form a true
  92. partition; they do not overlap and must cover the time line.  
  93. However the associated intervals may be defined in any way.  
  94.  
  95. One example of valid-time partitioning is to divide the time-line into
  96. years, based on the Gregorian calendar. Then for each year, compute
  97. the count of the tuples which overlap that year.
  98.  
  99. There is no existing term for this concept.  There is no partitioning
  100. attribute in valid-time partitioning, since the partitioning does not
  101. depend on attribute values, but instead on valid-times.
  102.  
  103. Valid-time partitioning may occur before or after value partitioning.
  104.  
  105. \subsection{Dynamic Valid-time Partitioning}
  106.  
  107. In {\em dynamic valid-time partitioning} the valid-time elements used
  108. in the partitioning are determined solely from the timestamps of the
  109. relation.
  110.  
  111. \entry{Alternative Names}
  112.  
  113. Moving window.
  114.  
  115. \entry{Discussion}
  116.  
  117. The term dynamic is appropriate (as opposed to static) because if 
  118. the information in the database changes, the partitioning intervals
  119. may change.  The intervals are determined from intrinsic information.
  120.  
  121. One example of dynamic valid-time partitioning would be to compute the
  122. average value of an attribute in a relation (say the salary
  123. attribute), for the previous year before the stop-time of each tuple.
  124. A technique which could be used to compute this query would be for
  125. each tuple, find all tuples valid in the previous year before the
  126. stop-time of the tuple in question, and combine these tuples into a
  127. set.  Finally, compute the average of the salary attribute values in
  128. each set.
  129.  
  130. It may seem inappropriate to use valid-time elements instead of
  131. intervals, however there is no reason to exclude valid-time elements.
  132. Perhaps the elements are the intervals during which the relation is
  133. constant.
  134.  
  135. The existing term for this concept  does not have an opposing term
  136. suitable to refer to static valid-time partitioning, and can not
  137. distinguish between the two types of valid-time partitioning (-E3, +E9).
  138. Various temporal query languages have used both dynamic and static
  139. valid-time partitioning, but have not always been clear about which
  140. type of partitioning they support (+E1).  Utilization of these terms
  141. will remove this ambiguity from future discussions.
  142.  
  143.  
  144. \subsection{Static Valid-time Partitioning}
  145.  
  146. \entry{Definition}
  147.  
  148. In {\em static valid-time partitioning} the valid-time elements used are
  149. determined solely from fixed points on a calendar, such as the start
  150. of each year.  
  151.  
  152. \entry{Alternative Names}
  153.  
  154. Moving window.
  155.  
  156. \entry{Discussion}
  157.  
  158.  
  159. This term further distinguishes existing terms (-E3, +E9).  It is an
  160. obvious parallel to dynamic valid-time partitioning (+E1).  Static is
  161. an appropriate term because the valid-time elements are determined
  162. from extrinsic information.  The partitioning element would not
  163. change if the information in the database changed.
  164.  
  165. Computing the maximum salary of employees during each month is an
  166. example which requires using static valid-time partitioning.  To compute
  167. this information, first divide the time-line into valid-time elements
  168. where each element represents a separate month on, say, the Gregorian
  169. calendar.  Then, find the tuples valid over each valid-time element,
  170. and compute the maximum aggregate over the members of each set.
  171.  
  172.  
  173. \subsection{Valid-time Cumulative Aggregation}
  174.  
  175. \entry{Definition}
  176.  
  177. In {\em cumulative aggregation}, for each valid-time element of the
  178. valid-time partitioning (produced by either dynamic or static valid-time
  179. partitioning), the aggregate is applied to all tuples associated with that
  180. valid-time element.
  181.  
  182. The value of the aggregate at any event is the value computed over the
  183. partitioning element that contains that event.
  184.  
  185. \entry{Alternative Names}
  186.  
  187. Moving window.
  188.  
  189. \entry{Discussion}
  190.  
  191. {\em Cumulative} is used because the interesting values are defined
  192. over a cumulative range of time (+E8).  This term is more precise than
  193. the existing term (-E3, +E9).  Instantaneous aggregation may be
  194. considered to be a degenerate case of cumulative aggregation where the
  195. partition is per chronon and the associated interval is that chronon.
  196.  
  197. One example of cumulative aggregation would be find the total number
  198. of employees who had worked at some point for a company.  To compute
  199. this value at the end of each calendar year, then, for each year,
  200. define a valid-time element which is valid from the beginning of time
  201. up to the end of that year.  For each valid-time element, find all
  202. tuples which overlap that element, and finally, count the number of
  203. tuples in each set.
  204.  
  205.  
  206. \subsection{Instantaneous Aggregation}
  207.  
  208. \entry{Definition}
  209.  
  210. In {\em instantaneous aggregation}, for each chronon on the valid
  211. time-line, the aggregate is applied to all tuples valid at that event.
  212.  
  213. \entry{Alternative Names}
  214.  
  215. None.
  216.  
  217. \entry{Discussion}
  218.  
  219. The term {\em instantaneous} is appropriate because the aggregate is
  220. applied over every chronon, every event.  It suggests an interest in
  221. the aggregate value over a very small time interval, an instant, much
  222. as acceleration is defined in physics over an infinitesimally small
  223. time (+R3).
  224.  
  225. Many temporal query languages perform instantaneous aggregation, others
  226. use cumulative aggregation, while still others use a combination of the two.
  227. This term will be useful to distinguish between the various alternatives,
  228. and is already used by some researchers (+R4,+E3).
  229.  
  230. \subsection{Gregorian Calendar}
  231.  
  232. \entry{Definition}
  233.  
  234. The {\em Gregorian calendar} is composed of 12 months, named in order,
  235. January, February, March, April, May, June, July, August, September,
  236. October, November, and December.  The 12 months form a year.  A year
  237. is either 365 or 366 days in length, where the extra day is used on
  238. ``leap years.''  Leap years are defined as years evenly divisible by 4, with
  239. centesimal years being excluded, unless that year is divisible by 400.
  240. Each month has a fixed number of days, except for February, the length
  241. of which varies by a day depending on whether or not the particular
  242. year is a leap year.
  243.  
  244.  
  245. \entry{Alternative Names}
  246.  
  247. None.
  248.  
  249. \entry{Discussion}
  250.  
  251. The Gregorian calendar is widely used and accepted (+E3,+E7).  This term is 
  252. defined and used elsewhere (-R1), but is in such common use in
  253. temporal databases that it should be defined.
  254.  
  255.  
  256. \end{document}
  257.